﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    //至少能装满多大的物品
    //状态表示：dp[i][j]表示在前i个物品中选择，体积不超过j，能够装的物品的最大价值
    //状态转移方程：dp[i][j] = max(dp[i - 1][j],dp[i][j - v[i]] + w[i],dp[i][j - 2 * v[i]] + 2 * w[i],dp[i][j - 3 * v[i]] + 3 * w[i] , ... , dp[i][j - k * v[i]] + k * w[i]);
    //分别为不选v[i]、选一个v[i]、选两个v[i]、... 、选k个v[i]
    //dp[i][j - v[i]] + w[i] = max(dp[i - 1][j - v[i]] + w[i],dp[i][j - 2 * v[i]] + 2 * w[i],dp[i][j - 3 * v[i]] + 3 * w[i],dp[i][j - 4 * v[i]] + 4 * w[i] , ... , dp[i][j - (k + 1) * v[i]] + (k + 1) * w[i]);
    //由于dp[i][j - k * v[i]] + k * w[i]) 和 dp[i][j - (k + 1) * v[i]] + (k + 1) * w[i])近似相等，因为j - k * v[i]接近于0，j - (k + 1) * v[i]，会小于0，舍弃
    //综上所述，dp[i][j] = max(dp[i - 1][j].dp[i][j - v[i]] + w[i]);
    //初始化：dp[0][i] = 0，没有选择物品，价值为0，dp[j][0]，j > 0，不用初始化，因为填这些位置的时候，状态转移方程不会越界
    //填表顺序：从上到下，从左往右
    //返回值：dp[m][n]
    int n, v;
    cin >> n >> v;

    vector<vector<int>> vw(n, vector<int>(2, 0));
    for (int i = 0; i < n; ++i)
    {
        cin >> vw[i][0] >> vw[i][1];
    }

    vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));
    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 0; j < v + 1; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= vw[i - 1][0])
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - vw[i - 1][0]] + vw[i - 1][1]);
            }
        }
    }

    cout << dp[n][v] << std::endl;

    //恰好装满
    //状态表示：dp[i][j]表示在前i个物品选择，体积恰好为j，物品的最大价值总和
    //状态转移方程：dp[i][j] = max(dp[i - 1][j],dp[i][j - v[i]] + w[i])
    //需要判断dp[i][j - v[i]]是不是-1
    //初始化：dp[0][0] = 0，表示价值为0,dp[0][i] = -1，表示不存在选择物品体积为i的，因为没有物品
    //dp[i][0]不要初始化
    //填表顺序：从左往右，从上到下
    //返回值：dp[n][v] == -1 ? 0 : dp[n][v]
    vector<vector<int>> Completedp(n + 1, vector<int>(v + 1, 0));

    for (int j = 1; j < v + 1; ++j)
    {
        Completedp[0][j] = -1;
    }

    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 0; j < v + 1; ++j)
        {
            Completedp[i][j] = Completedp[i - 1][j];
            if (j >= vw[i - 1][0] && Completedp[i][j - vw[i - 1][0]] != -1)
            {
                Completedp[i][j] = max(Completedp[i - 1][j], Completedp[i][j - vw[i - 1][0]] + vw[i - 1][1]);
            }
        }
    }

    cout << (Completedp[n][v] == -1 ? 0 : Completedp[n][v]) << endl;
}

/*
描述
你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为vi,价值为wi。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数vi和wi，表示第i种物品的体积和价值。1≤n,V≤1000

输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1
输入：
2 6
5 10
3 1
输出：
10
2
*/

